(1) Field of the Invention
The present invention relates to an image data encoding and decoding system, and more particularly to a pattern encoding and decoding method and an encoder and a decoder using the same method, which enables the reduction in codes in pattern encoding.
(2) Description of the Related Art
An encoding method using pattern matching is well known in the prior art for encoding binary image data including mainly character images.
In the prior art method, character images are extracted in small units, for instance, in character-by-character units, from image data (extracted images being hereinafter referred to as "patterns"). Such patterns are extracted by a well-known method such as a boundary tracing method.
Each pattern is compared with preliminarily prepared character image data (hereinafter referred to as "library"). When the same character as the pattern is in the library, the extracted character image is not encoded, but an index number of this character image (index number data) and a position data representing the position of the character image in the image data are encoded. In this way, the encoding efficiency can be improved.
For encoding the above index data and position data, well-known encoding methods such as arithmetic encoding are frequently adopted. For example, "Lossless and Lossy Compression of Test Images by Soft Pattern Matching" uses, for index number data and position data encoding, codes which are developed from the arithmetic encoding method so as to permit processing of multivalue data such as numerical data (called "multi-symbol arithmetic codes").
The index number data and the position data increase proportionally with an increase in the number of patterns. This means that, in the case of image data in which there is a possibility for the number of patterns to become extremely large such as when the image data contains Japanese characters, the amount of data to be encoded will inevitably be large.
As shown, in the above prior art encoding system, when the number of patterns becomes large in encoding a character image using pattern matching, the index number data and the position data will inevitably be large. As a consequence, the proportion of the total code is occupied by the index number data and the position data becomes large, resulting in the deterioration of encoding efficiency. Accordingly, there has been a need for a method which enables efficient encoding of the index number data and the position data.